package top

import (
	"sort"
	"strconv"
)

// Matchsticks to Square，数组能否组成一个正方形
func makesquare(matchsticks []int) bool {
	var sum = 0
	for _, v := range matchsticks {
		sum += v
	}
	if sum%4 != 0 {
		return false
	}
	sort.Ints(matchsticks)

	return dfsSquare(matchsticks, make([]int, 4), len(matchsticks)-1, sum/4)
}

func dfsSquare(nums, sums []int, index, target int) bool {
	if index == -1 {
		if sums[0] == target && sums[1] == target && sums[2] == target {
			return true
		}
		return false
	}
	for i := 0; i < 4; i++ {
		if sums[i]+nums[index] > target {
			continue
		}
		sums[i] += nums[index]
		if dfsSquare(nums, sums, index-1, target) {
			return true
		}
		sums[i] -= nums[index]
	}

	return false
}

/**
 * @description: Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
 * @return: 括号的组合数量
 * @author: kami
 * @关键词：递归
 * @date: 2021/6/27 21:49
 */
func generateParenthesis(n int) []string {
	result := make([]string, 0)
	var sign []byte
	backtrack(&result, sign, 0, 0, n)
	return result
}

func backtrack(result *[]string, sign []byte, open, close, max int) {
	if len(sign) == max*2 {
		*result = append(*result, string(sign))
		return
	}
	if open < max {
		backtrack(result, append(sign, '('), open+1, close, max)
	}
	if close < open {
		backtrack(result, append(sign, ')'), open, close+1, max)
	}
}

/*
最长回文字符串
*/
func longestPalindromes(str string) string {
	//size := len(str)

	return ""
}

/*
最长回文字符串:中心向两边 o（n2）babad
*/
func longestPalindromesDoubleSingle(str string) string {
	size := len(str)
	var res = str[0:1]
	for i := 0; i < size-1; i++ {
		str1 := findLongestPalindromes(str, size, i, i)
		str2 := findLongestPalindromes(str, size, i, i+1)
		curStr := ""
		if len(str1) > len(str2) {
			curStr = str1
		} else {
			curStr = str2
		}
		if len(curStr) > len(res) {
			res = curStr
		}

	}
	return res
}

func findLongestPalindromes(str string, size, low, high int) string {
	for low >= 0 && high < size {
		if str[low] == str[high] {
			low--
			high++
			continue
		}
		break
	}
	low++
	if low < 0 {
		low = 0
	}

	if high > size {
		high = size
	}
	return str[low:high]
}

/*
一个数组[15,20,25,30]，一个list[10,12,16,18,23,22,17,33]分别找出<15，15<x<20,20<x<25
*/
func groupNums(groups []int, nums []int) map[string][]int {
	sort.Ints(nums)
	size := len(nums)
	sizeG := len(groups)
	idxG := 0
	idxNum := 0
	res := make(map[string][]int)
	for i := 0; i < size; i++ {
		for idxG < sizeG && nums[i] > groups[idxG] {
			idxG++
		}
		if idxG >= sizeG && i < size {
			idxNum = i
			break
		}
		if idxG == 0 {
			res["<"+strconv.Itoa(groups[0])] = append(res["<"+strconv.Itoa(groups[0])], nums[i])
		} else {
			str := strconv.Itoa(groups[idxG-1]) + "<" + strconv.Itoa(groups[idxNum])
			res[str] = append(res[str], nums[i])
		}
	}

	if idxNum < size {
		var str = ">" + strconv.Itoa(groups[0])
		for i := idxNum; i < size; i++ {
			res[str] = append(res[str], nums[i])
		}
	}
	return res
}
